# Definition for singly-linked list.
class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None


class Solution:
  def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    head_1, head_2 = l1, l2
    vals = []
    if l1 == None:
      return l2
    if l2 == None:
      return l1
    while head_1 is not None and head_2 is not None:
      if head_1.val == head_2.val:
        vals.append(head_1.val)
        vals.append(head_2.val)
        head_1 = head_1.next
        head_2 = head_2.next
      elif head_1.val < head_2.val:
        vals.append(head_1.val)
        head_1 = head_1.next
      elif head_2.val < head_1.val:
        vals.append(head_2.val)
        head_2 = head_2.next
    while head_1 is not None:
      vals.append(head_1.val)
      head_1 = head_1.next
    while head_2 is not None:
      vals.append(head_2.val)
      head_2 = head_2.next
    res = ListNode(vals[0])
    res_head = res
    for i in range(1, len(vals)):
      res.next = ListNode(vals[i])
      res = res.next
    return res_head


'''
STATUS: SOLVED
TRIES:  1
TIME:   76 MS
MEMORY: 14.5 MB
'''
if __name__ == "__main__":
  solution = Solution()
  l1 = ListNode(1)
  l2 = ListNode(1)
  l1_sav, l2_sav = l1, l2
  l1_vals, l2_vals = [1, 3, 4, 5], [1, 5, 6, 7]
  for i in range(1, len(l1_vals)):
    l1.next = ListNode(l1_vals[i])
    l1 = l1.next
  for j in range(1, len(l2_vals)):
    l2.next = ListNode(l2_vals[j])
    l2 = l2.next
  res = solution.mergeTwoLists(l1=l1_sav, l2=l2_sav)
  while res is not None:
    print(res.val, end=', ')
    res = res.next
